package com.ssh;

import java.util.Arrays;

import org.junit.Test;

public class ThreeSumClosest_16 {
	public int threeSumClosest(int[] nums, int target) {
		Arrays.sort(nums);
		int y = 0,x = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length-2; i++) {
        	int ho = i+1,hi = nums.length-1,s = target-nums[i];
        	if (i == 0 || nums[i] != nums[i-1]) {
        		while (ho < hi) {
        			if (nums[ho] + nums[hi] == s) {
        				return target;
        			}else if (nums[ho] + nums[hi] <= s ) {
        				if (x > Math.abs(s-(nums[ho]+nums[hi]))) {
        					x = Math.abs(s-(nums[ho]+nums[hi]));
        					y = nums[i]+nums[ho]+nums[hi];
        				}
        				ho++;
        			}else {
        				if (x > Math.abs(s-(nums[ho]+nums[hi]))) {
        					x = Math.abs(s-(nums[ho]+nums[hi]));
        					y = nums[i]+nums[ho]+nums[hi];
        				}
        				hi--;
        			}
        		}
        	}
        }
        return y;
	}
	@Test
	public void test () {
		int[] nums = {1, 1, 1, 0};
		System.out.println(threeSumClosest(nums,-100));
	}
}
